#include <stdio.h>
#include <assert.h>
#include <iostream>
using namespace std;


typedef char DataType;
struct ListNode
{

    DataType _data;
    ListNode * _next;
    ListNode(DataType value):_data(value),_next(NULL)
    {}
};

ListNode * PushFront(ListNode ** ListHead,DataType value)
{
    assert(ListHead);
    if(*ListHead==NULL)
    {
        *ListHead=new ListNode(value);
        return *ListHead;
    }
    ListNode *new_node=new ListNode(value);
    new_node->_next=*ListHead;
    *ListHead=new_node;
    return new_node;
}
void EraseNode(ListNode **ListHead ,ListNode * to_delete)
{
    assert(ListHead);
    if(*ListHead==NULL)
    {
        return;
    }

    //1.处理删除的单链表只有一个节点，并且是要删除的节点
    if(((*ListHead)->_next==NULL)&&(to_delete==*ListHead))
    {
        delete *ListHead;
        *ListHead=NULL;
        return;
    }

    //2.如果要删除的节点为单链表的最后一个节点，只能遍历整个单链表
    if(to_delete->_next==NULL)
    {
        ListNode *cur=*ListHead;
        while(cur->_next!=to_delete)
        {
            cur=cur->_next;
        }
        //出循环，说明cur为要删除节点的前一个节点
        cur->_next=to_delete->_next;
        delete to_delete;
        return;
    }
    //3.处理普通的情况
    ListNode *to_erase=to_delete->_next;
    swap(to_erase->_data,to_delete->_data);
    to_delete->_next=to_erase->_next;
    delete to_erase;
}

void ListPrint_char(ListNode *ListHead)
{
    if(ListHead==NULL)
    {
        return;
    }
    ListNode *cur=ListHead;
    while(cur!=NULL)
    {
        printf("%c->",cur->_data);
        cur=cur->_next;
    }
    printf("NULL\n");
}
void DestroyList(ListNode **ListHead)
{
    assert(ListHead);
    if(*ListHead==NULL)
    {
        return;
    }
    ListNode *cur=*ListHead;
    while(cur!=NULL)
    {
        ListNode * to_delete=cur;
        cur=cur->_next;
        delete to_delete;
    }
    *ListHead=NULL;
}
void TestEraseNode()
{
    ListNode *ListHead=NULL;
    ListNode * pos_e=PushFront(&ListHead,'e');
    ListNode * pos_d=PushFront(&ListHead,'d');
    ListNode * pos_c=PushFront(&ListHead,'c');
    ListNode * pos_b=PushFront(&ListHead,'b');
    ListNode * pos_a=PushFront(&ListHead,'a');


    ListPrint_char(ListHead);
    printf("删除节点e\n");
    EraseNode(&ListHead ,pos_e);
    ListPrint_char(ListHead);
    printf("删除节点d\n");
    EraseNode(&ListHead ,pos_d);
    ListPrint_char(ListHead);
    printf("删除节点c\n");
    EraseNode(&ListHead ,pos_c);
    ListPrint_char(ListHead);
    printf("删除节点b\n");
    EraseNode(&ListHead ,pos_b);
    ListPrint_char(ListHead);
    printf("删除节点a\n");
    EraseNode(&ListHead ,pos_a);
    ListPrint_char(ListHead);
    DestroyList(&ListHead);
    ListPrint_char(ListHead);
}
int main()
{
    TestEraseNode();
    return 0;
}
